1. Field of the Invention
The invention relates to the field of electronic sorting networks and methodologies, and in particular to sorting networks, analogous to a Batcher merging circuit, which networks use comparators for sorting.
2. Description of the Prior Art
It is often necessary in a wide variety of computer operations and applications to sort among a plurality of inputs to order them or sort them into a hierarchical order such as in an alphanumeric ascending or descending series. The speed and size of the circuitry required to perform such a sort of this type often becomes an important parameter or limitation in the implementation of some larger process or apparatus.
Sorting methods and circuits may be classified as comparator-based or not. Among the comparator-based methodologies and circuits there are those which utilize feedback and those which do not. A comparator-based methodology and circuit which utilizes feedback is one in which the choice of a pair of data input items which are to be next compared is influenced by the history of previous comparison outcomes.
Methodologies and circuits which do not utilize feedback are more commonly described as simply networks for sorting. A typical prior art sorting network is diagrammatically depicted in FIG. 1. FIG. 1 shows a circuit for comparison of four words, X.sub.0, X.sub.1, Y.sub.0 and Y.sub.1. The four pairs of parallel input lines 16 and 18 are cross-coupled on a pair-wise fashion by comparator circuits 10 and 12, followed by crosspair connections through comparator circuit 14. FIG. 1 has been shown with two equivalent symbologies. On the left side is a very highly diagrammatic depiction of the network where vertical lines represent the comparators and the network lines are shown as unbroken horizontal lines. The actual physical circuit is more faithfully depicted by the equivalent depiction on the right side of FIG. 1 where the comparators are shown as blocks and the network lines are not continuous, but begin and terminate with a comparator. It turns out, however, that the topology of the circuit is more readily visualized in the style of the more abstract depiction, which will be used in the remaining Figures. The general taxonomy of sorting methodologies is described in Chapter 5 of Knuth, "SORTING AND SEARCHING," Vol. 3, "ART OF COMPUTER PROGRAMMING," Addison-Wesley, Reading, Mass. (1973).
The absence of any feedback as shown in a prior art sorting network of FIG. 1 allows such circuits to be implemented with low level hardware and allows for parallel implementation. However, in feedback free circuits, it has been difficult to obtain a sorting network with a number of comparators of an order equal to or less than N log.sub.2 N, where N is the number of data inputs. Although it has been theoretically determined that a sorting network of the order of N log.sub.2 N comparators with a delay of the order of log.sub.2 N does exist, explicit construction or examples of such networks have yet to be given. Therefore, as a practical matter, feedback free networks are still built along the lines of classical Batcher networks which have a delay of approximately 1/2 (log.sub.2 N).sup.2. See for example K. E. Batcher, "SORTING NETWORKS AND THEIR APPLICATIONS," Proceedings 1968 Spring joint COMP Conf. at pages 307-14, AFIPS Press, 1968.
Sequential balanced networks, such as described by Dowd, et al, "THE SEQUENTIAL BALANCED SORTING NETWORK," New Jersey Institute of Technological Research Report No. 10 describes the sequential balanced network in which data is passed sequentially log.sub.2 N times through design whose delay time is log.sub.2 N.
The material design features for a network are:
(1) Ease of specification of the network for any number of data items; PA1 (2) Succinctness and understandability of verification; PA1 (3) Minimal delay; PA1 (4) Repeated sequential use of a single design; PA1 (5) Minimal total number of comparators; and PA1 (6) Minimal total number of different lengths among the comparators.
An AKS network achieves a delay (feature 3) through the network of the order of c log.sub.2 N, where c is a very large number, minimizes the number of comparators (feature 5), but has poor or unknown performance in each of the other four design categories. See Ajtai, et al, "AN ORDER OF N LOG N SORTING NETWORK," Proc. 15th Annual ACM Symposium on the Theory of Computing (SIGACT) Boston (1983).
The sequential balanced network described above and shown as FIG. 6 has a simple specification of the network for any number of data items, but has a large number of total different lengths among the comparators, for example, one finds all possible odd lengths.
An odd-even transposition network (Knuth, supra, Chapter 5) is very easy to specify, has repeated sequential use of a single design and a single length among the comparators, but performs poorly with respect to each of the other categories.
What is needed then is a sorting network that performs well in each of these categories without any particular mark or significant disadvantage in any one of them.